package main.java.LeetCode.ClassicalAlgorithm.Sort.Impl;


import main.java.LeetCode.ClassicalAlgorithm.Sort.Sort;

@SuppressWarnings("ALL")
public class HeapSort implements Sort {
    private final String NAME = "HeapSort";
    @Override
    public void sort(int[] arr) {
        doSort(arr,0, arr.length-1);
        System.out.print(NAME+": ");
        for(int num:arr){
            System.out.print(num+" ");
        }
        System.out.println();

    }

    private void doSort(int[] arr,int start,int end){
        AdjustHeap(arr);
        while (start<end){
            heapify(arr,start,end);
            swap(start,end,arr);
            end--;
        }

    }
    private void AdjustHeap(int[] arr){
        int len = arr.length-1;
        boolean isChange = false;

        while (true) {
            for (int i = len; i > 0; i--) {
                int index = (i - 1) / 2;
                if (arr[i] > arr[index]) {
                    swap(i, index, arr);
                    isChange = true;
                }
            }
            if(!isChange){
                break;
            }else
                isChange = false;
        }
    }
    private void heapify(int[] arr,int start,int end){
        int flag = start;
        int leftV = 0;
        int rightV = Integer.MIN_VALUE;
        int maxIndex = 0;
        while (flag<=end){
            int left = ((flag+1)*2)-1;
            if(left<=end)
                leftV = arr[left];
            else
                return;

            int right = (flag+1)*2;
            if(right<=end) {
                rightV = arr[right];
                maxIndex = leftV >= rightV ? left : right;
            }else
                maxIndex = left;


            if(arr[maxIndex]>arr[flag])
                swap(maxIndex,flag,arr);
            else
                return;
            flag = maxIndex;
        }
    }
    private void swap(int index1,int index2,int[] arr){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
